package com.lenl.arithmetic.search;

import java.util.Arrays;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-05-02 17:16
 * @description 斐波那契查找 黄金分隔点
 */
public class FibonacciSearch {
    public static void main(String[] args) {
        int[] arr={1,8,10,89,1000,1234};
        System.out.println("index="+fibSearch(arr,1));
    }
    //因为后后面mid=low+F(k-1)+1,需要用到斐波那契数列，因此需要先获取到一个斐波那契数列
    //非递归方法获取
    public static int[] fib(int maxSize){
        int[] f=new int[maxSize];
        f[0]=f[1]=1;
        for (int i=2;i<maxSize-1;i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f;
    }
    //编写斐波那契查找算法
    //非递归方式
    /**
     *
     * @param a 数组
     * @param key 查找值
     * @return 返回下标，没有-1
     */
    public static int fibSearch(int[] a,int key){
        int low=0;
        int high=a.length-1;
        int k=0;//表示斐波那契分割数值的下标
        int mid=0;//存放mid值
        int[] f=fib(20);//获取斐波那契数列
        //找到斐波那契分割数值的下标
        while(high>f[k]-1){
            k++;
        }
        //因为f[k]值可能大于数组a的长度，因此我们需要arrays类构造新的数组，并指向temp[]
        //不足的部分会使用0填充
        int[] temp= Arrays.copyOf(a,f[k]);
        //实际上需要使用a数组最后的数填充temp
        for(int i=high+1;i<temp.length;i++){
            temp[i]=a[high];
        }

        //使用while循环处理，找到key
        while(low<=high){
            mid=low+f[k-1]-1;
            if(key<temp[mid]){
                //继续向左边查找
                high=mid-1;
                //全部元素=前面的元素+后面的元素
                //f[k]=f[k-1]+f[k-2]
                //因为前面有f[k-1]个元素，所以可以继续拆分 f[k-1]=f[k-2]+f[k-3]
                //即在f[k-1]的前面继续查找k--
                //即下次循环mid=f[k-1-1]-1
                k--;
            }else if(key>temp[mid]){
                low=mid+1;
                //全部元素=前面的元素+后面的元素
                //f[k]=f[k-1]+f[k-2]
                //后面有f[k-2]个元素 所以可以继续拆分 f[k-1]=f[k-3]+f[k-4]
                //即在f[k-2]前面进行查找 k-=2
                //即下次循环mid=f[k-1-2]-1
                k-=2; //这里的黄金分隔前面多，后面少
            }else{
                //找到
                //需要确定返回的哪个下标
                if(mid<=high){
                    return mid;
                }else{
                    return high;
                }
            }
        }

        return -1;



    }
}
